The present invention relates to a method and to an apparatus for transferring information through a communication medium. More particularly, the present invention relates to a method and to an apparatus for scheduling the transmission of information across connections in a communication system.
Various systems have been adopted to carry digitally-encoded signals for communication applications, such as, telephone, video, and data services. These systems are often connection-oriented packet mode transmission systems, such as, asynchronous transfer mode (ATM) systems, frame relay systems, X.25 systems, or other transmission systems. Connection-oriented systems (e.g., ATM systems) have been employed in private and public communication systems or networks (e.g., wide area networks (WANs)) to transfer packetized signals (e.g., data cells or protocol data units) across communication lines, such as, telephone lines, cables, optical fibers, air waves, satellite links, or other communication media.
As an example, the ATM system transfers the data cells or units across the ATM system via connections or channels. The data cells can represent voice, sound, video, graphics, data, or combinations thereof for use in computing or communication applications. The connections can be part of a single physical link carrying a number of logical connections or be a single isolated path. The connections are often classified as either virtual channel connections (VCC), or virtual path connections (VPC) and either permanent virtual connections (PVC), or switched virtual connections (SVC). Connections are generally defined by a source and a destination for the data cell.
ATM systems or networks are generally utilized to support the integration of high quality voice, video, and high speed data traffic which can have specific conformance and quality of service (QOS) requirements. A scheduler is employed to properly select connections for transmission in accordance with operational parameters, such as, QOS requirements. The scheduler organizes transmission of data cells associated with the connections to guarantee QOS requirements and protocol conformance at the network ingress point as well as to maximize bandwidth for the communication system.
ATM systems can utilize at least four types of service categories or modes of traffic for transmission of data cells on connections. These four types include the constant bit rate (CBR) mode, the variable bit rate (VBR) mode, the unspecified bit rate (UBR) mode, and the available bit rate (ABR) mode. Each of these modes have somewhat different transmission protocol requirements. For example, the CBR mode requires that a connection be able to send a specific number of cells or bits per second; the CBR mode must have a set end-to-end bandwidth. The CBR mode is often utilized for data sources, such as, voice or video circuits which are susceptible to cell delay variations (CDV). The VBR mode often utilizes a xe2x80x9csingle leaky bucketxe2x80x9d algorithm (e.g., virtual scheduling algorithm) or xe2x80x9cdual leaky bucketxe2x80x9d algorithm. Although the VBR mode has somewhat more flexible timing requirements than the CBR mode, the VBR mode must meet timing requirements dictated by the single or dual bucket algorithms. The ABR mode requires the sending of data cells in response to feedback from the network.
To appropriately supply and maximize the effectiveness of the transmission of the CBR, UBR, ABR, and VBR modes of traffic on the network, a scheduler controls a segmentation coprocessor (e.g., segmentation and reassembly unit) to direct communication of data cells or data protocol units on the connections. Generally, the scheduler attempts to select particular connections for transmission at particular times to guarantee conformance to traffic contracts and to QOS at network ingress points. This selection process, or scheduling, selects various connections for transmission based upon operational parameters associated with each connection, with feedback from the network, and with traffic mode timing requirements.
Scheduling a large number of connections with particular timing and communication criteria can lead to complex scheduling problems. For example, various connections can need a particular capacity from the network, and the availability of the particular capacity can be impinged by congestion across the network. These scheduling problems can be compounded by the specific requirements of CBR mode, VBR mode, UBR mode, and ABR modes of traffic.
Traditional network scheduling algorithms, such as, Token Ring and Ethernet utilize fairly simplified scheduling algorithms. The algorithms are typically based upon transmission schemes wherein each member of the network gets a fair share of the network bandwidth. These systems cannot handle QOS requirements or the four categories (e.g., CBR mode, VBR mode, UBR mode, and ABR mode) of traffic for ATM systems.
Prior schedulers utilized in ATM systems access a fixed size schedule table to assist time scheduling of connections. The fixed schedule table is comprised of slots, each of which is assigned to particular connections. The scheduler processes each slot one-by-one and transmits the connection assigned to the slot being processed to the network. These prior schedulers are somewhat inflexible and prioritize CBR and VBR modes traffic. Further, the fixed schedule table requires that the CBR modes of traffic be sent a fixed rate or harmonic of a fixed rate. Further still, these prior schedulers often must send idle cells to maintain the drain rate for the connection.
Other prior schedulers utilize a first-in, first-out (FIFO) memory and a timer (e.g., hardware units) to appropriately send connections across the network. However, the number of hardware units is limited by circuit size design criteria and cannot be dynamically allocated as bandwidth becomes available. Each FIFO and timer must be dedicated to a particular rate of transmission. Therefore, the rates of transmission are limited. Additionally, these prior schedulers cannot prioritize VBR and CBR modes of traffic.
U.S. patent application Ser. No. 08/759,057 filed Dec. 2, 1996, by Lincoln, entitled xe2x80x9cScheduler Utilizing Dynamic Schedule Tablexe2x80x9d dynamically manages and prioritizes modes of traffic. The communication system can be arranged as an asynchronous transfer mode (ATM) system which can efficiently handle the CBR mode of traffic, the VBR mode of traffic, the UBR mode of traffic, and the ABR mode of traffic. Further, both the CBR mode of traffic and the VBR mode of traffic can be handled on a dynamic basis.
Conventional schedulers do not support a guaranteed frame rate (GFR) mode of traffic. The GFR mode can also be referred to as UBR plus mode. A scheduler with GFR mode guarantees each session a minimum rate of service while sharing excess bandwidth and providing a global maximum rate. One possible method for achieving a guaranteed frame rate would be to take half of the cells from every frame and pass them through. This hypothetical method is flawed, though, because although it may result in a satisfactory minimum cell rate (MCR), complete frames (e.g., group of cells) are not passed and proper packet switched communication requires transfer of entire frames, not just parts or cells. The GFR mode ensures MCR for entire frames of data, rather than just cells of data. In this way, the GFR mode ensures that communication time is not wasted because only portion of frames (which have to be discarded) are communicated. Additionally conventional schedulers cannot efficiently schedule a plurality of tunnel modes.
Thus, there is a need for a scheduler which can support a guaranteed frame rate (GFR). Additionally, there is a need for a scheduler for an asynchronous transfer mode (ATM) system which can support additional service classes, including the CBR mode of traffic the VBR mode of traffic, the UBR mode of traffic, and the ABR mode of traffic. Further still, there is a need for a scheduler which can handle frame relay and ATM service, along with GFR mode. Even further still, there is a need for a scheduler which can provide a minimum frame rate and provide fair sharing among connections for excess bandwidth. Yet further, there is a need for a scheduler which limits the total GFR connections to a peak cell rate. Still further, there is a need for a scheduler which utilizes VBR shaping and priority queues to obtain a MCR. Yet even further, there is a need for a scheduler which can service two or more tunnel modes so parallel traffic shaping and prioritized tunnel connections, such as tunnel within a tunnel, can be achieved.
The present invention relates to a traffic manager coupled to a communication system for scheduling transmission of information associated with a plurality of connections in the communication system. The traffic manager includes a priority queue, a connection data structure, and a scheduler. The connection data structure includes a guaranteed bit rate field for each connection. The scheduler is coupled to the connection data structure and the priority queue. The scheduler loads information from the data structure to the queue, wherein the scheduler shapes the connection for a minimum cell rate and allows use by the connection of excess bandwidth if the guaranteed bit rate field is set.
The present invention still further relates to a communication system including a control memory and scheduler. The control memory includes a priority queue and a connection data structure. The priority queue has at least one tunnel entry. The connection data structure includes a guaranteed bit rate field for each connection. Each connection uses a particular bit rate mode of traffic. Particular bit rate mode parameters for the connection are included in the connection data structure. The scheduler is coupled to the connection data structure. The scheduler schedules a plurality of connections from the at least one tunnel entry to select a connection for eventual transmission. The scheduler also dynamically reschedules the connection in response to a timing parameter, the particular bit rate mode parameters for the connection, and the guaranteed bit rate field.
The present invention further relates to a method of scheduling connections for transmission on a communication network having a first tunnel and a second tunnel. In the method, the scheduler increments a first tunnel counter associated with the first tunnel when a connection is processed. Then, the scheduler sets the first tunnel active when the first tunnel counter is above a first threshold. The scheduler also increments a second tunnel counter associated with the second tunnel when a connection is processed. Then, the scheduler sets the second tunnel active when the second tunnel counter is above a second threshold. Finally, the scheduler determines whether the first and second tunnels are processed.
The present invention still further relates to a traffic manager coupled to a communication system for scheduling transmission of information associated with a plurality of connections in the communication system. The traffic manager includes a schedule table, a priority queue, and a scheduler. The schedule table includes a plurality of slots. The priority queue includes at least one tunnel entry. The scheduler is coupled to the schedule table. The scheduler processes the slots. The scheduler activates the tunnel when a number of slots are processed where the number exceeds a threshold. The scheduler provides a connection associated with the tunnel entry for transmission of information when the tunnel entry is activated.
According to one exemplary aspect of the present invention, a scheduler provides a guaranteed frame rate (GFR). With GFR, each communication session is guaranteed a minimum rate of service while fairly sharing excess bandwidth and providing global maximum rate. Also, the scheduler supports a minimum cell rate (MCR) using priority bumping, where priority levels for communication states are adjusted before scheduling. Parallel traffic shaping is also provided to accommodate simultaneous scheduling to MCR with scheduling of excess bandwidth.
According to yet another exemplary aspect of the present invention, a scheduler provides GFR and supports other service classes, including the CBR mode of traffic, VBR mode of traffic, the UBR mode of traffic, and the ABR mode of traffic. Scheduling modes of operation can include but are not limited to, guaranteed frame rate (GFR), constant bit rate (CBR). Scheduling modes of operation can include, but are not limited to, guaranteed frame rate (GFR), constant bit rate (CBR). Further, the scheduler provides tunnels for any service class (UBR, VBR single and dual, ABR and GFR). The present invention further relates to a method of scheduling connections for transmission on a communication network having a first tunnel and a second tunnel. In the method a first counter associated with the first tunnel is incremented when a connection is processed. Then, the scheduler sets the first tunnel active when the first tunnel counter is above a first threshold. The scheduler also increments a second tunnel counter associated with the second tunnel when a connection is processed. Then, the scheduler sets the second tunnel active when the second tunnel counter is above a second threshold. Finally, the scheduler determines whether the first and second tunnels are processed.
The present invention still further relates to a traffic manager coupled to a communication system for scheduling transmission of information associated with a plurality of connections in the communication system. The traffic manager includes a schedule table, a priority queue, and a scheduler. The schedule table includes a plurality of slots. The priority queue includes at least one tunnel entry. The scheduler is coupled to the schedule table. The scheduler processes the slots. The scheduler provides a connection associated with the tunnel entry for transmission of information when the tunnel entry is activated.
In the present application, the term communicate refers to any of the following: receive, provide, transmit, obtain, send, input, output, or convey.